/*
 * @lc app=leetcode.cn id=475 lang=cpp
 *
 * [475] 供暖器
 */

// @lc code=start
class Solution
{
public:
    int serachtwo(vector<int> &heaters, int m)
    {
        //需要找到一个值比m大
        int left = 0;
        int right = heaters.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2; //避免溢出
            if (heaters[mid] > m)
            {
                left = mid + 1;
            }
            else if (heaters[mid] < m)
            {
                right = mid - 1;
            }
        }
        return left;
    }
    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        //一条线 多个圈覆盖所有范围
        //找到所有东西距离最近的圆心的最短距离
        //这个查找用二分查找会快 否则就会超时间
        //sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int res = 0;
        for (int i = 0; i < houses.size(); i++)
        {
            int right = heaters.size() - 1;
            int left = 0;
            for (int j = 0; j < heaters.size(); j++)
            {
                //找到第一个右边的
                right = serachtwo(heaters, houses[i]);
            }
            left = right - 1;
            //如果没有找到更大的 right为最右边的供暖
            //如果只有一个供暖器那么left = -1 right =0
            if (left == -1)
            {
                //只有一个供暖
                res = max(res, abs(houses[i] - heaters[0]));
            }
            else
            {
                //能找到两个供暖
                int tmp = min(abs(houses[i] - heaters[left]),
                              abs(houses[i] - heaters[right]));
                res = max(res, tmp);
            }
        }
        return res;
    }
};
// @lc code=end
